package com.data.construct.array;

/**
 * 环形数组实现
 * 可以解决数组头部增/删元素, 时间复杂度有O(n) 简化为 O(1)的问题
 * 环形数组的区间被定义为左闭右开的, 是最方便处理的。
 *
 * @author sunhl
 * @Description:
 * @Date: created in 2024/10/28 0028 10:36
 * @Modified By:
 */
public class CycleArray<T> {
    private T[] arr;

    /**
     * 数组的起始指针(不再是0了, 这一点很重要)
     * 另外起始指针是闭区间(第一个元素的索引位置)
     */
    private int start;

    /**
     * 数组的结束指针(不再是count - 1了, 这一点很重要)
     * 另外结束指针是开区间(最后一个元素的下一个索引位置)
     */
    private int end;

    private int count;

    private int size;

    public CycleArray() {
        this(1);
    }

    @SuppressWarnings("unchecked")
    public CycleArray(int size) {
        this.size = size;
        // 因为 Java 不支持直接创建泛型数组，所以这里使用了类型转换
        this.arr = (T[]) new Object[size];
        // start 指向第一个有效元素的索引，闭区间
        this.start = 0;
        // 切记 end 是一个开区间，
        // 即 end 指向最后一个有效元素的下一个位置索引
        this.end = 0;
        this.count = 0;
    }

    // 在数组头部添加元素，时间复杂度 O(1)
    public void addFirst(T val) {
        // 当数组满时，扩容为原来的两倍
        if (isFull()) {
            resize(size * 2);
        }
        // 因为 start 是闭区间，所以先左移，再赋值
        // 这里要加size, 是防止start为0, 会算出负数, 不循环了
        start = (start - 1 + size) % size;
        arr[start] = val;
        count++;
    }

    // 获取头部元素
    public T getFirst() {
        return arr[start];
    }

    // 删除数组头部元素，时间复杂度 O(1)
    public T removeFirst() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }
        // 因为 start 是闭区间，所以先赋值，再右移
        T result = arr[start];
        arr[start] = null;
        start = (start + 1) % size;
        count--;
        // 如果数组元素数量减少到原大小的四分之一，则减小数组大小为一半
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }

        return result;
    }

    // 在数组尾部添加元素，时间复杂度 O(1)
    public void addLast(T val) {
        if (isFull()) {
            resize(size * 2);
        }
        // 因为 end 是开区间，所以是先赋值，再右移
        arr[end] = val;
        end = (end + 1) % size;
        count++;
    }

    // 获取尾部元素
    public T getLast() {
        if (end > 0) {
            return arr[end - 1];
        } else {
            return arr[0];
        }
    }

    // 删除数组尾部元素，时间复杂度 O(1)
    public T removeLast() {
        if (isEmpty()) {
            throw new IllegalStateException("Array is empty");
        }

        // 因为 end 是开区间，所以先左移，再赋值
        // 需要单独加size也是为了防止负数
        end = (end - 1 + size) % size;
        T result = arr[end];
        arr[end] = null;
        count--;
        // 缩容
        if (count > 0 && count == size / 4) {
            resize(size / 2);
        }

        return result;
    }


    // 一些工具方法
    // 自动扩缩容辅助函数
    @SuppressWarnings("unchecked")
    private void resize(int newSize) {
        // 创建新的数组
        T[] newArr = (T[]) new Object[newSize];
        // 将旧数组的元素复制到新数组中
        for (int i = 0; i < count; i++) {
            newArr[i] = arr[(start + i) % size];
        }
        arr = newArr;
        // 重置 start 和 end 指针
        start = 0;
        // end是开区间, 所以用count而不count-1
        end = count;
        size = newSize;
    }

    public boolean isFull() {
        return count == size;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

}
